The streaming media is a multimedia transmission method over a network. When a server receives a request of watching video/audio data from a client, the server decomposes the video/audio data into multiple small packets and sends each packet to the client; and then the applications on the client end reorganize these received packets to render the reconstructed video/audio data in real-time on the display device of the client site. Thus the endless supplying of the video/audio data flows from the server to the client site, and results in a continuous video/audio stream. This multimedia transmission method is usually called as streaming media.
For the client, the transmission method of streaming media may shorten the delay time of watching the selected video/audio data content. The client may easily determine whether the video/audio data content received for watching is preferred or not, without having to spend a lot of money and time to download useless data. Thus the client may easily watch the data content on-demand as using the home TV or the video recording device, and the data content received may be rewound fast forward or backward, to make viewing Internet video/audio more accessible. For a content provider, a well-designed method of streaming media only transmits data for rendering, without leaving any permanent copy at the client side. This may also ensure the rights of copyright holder.
With the popularization of broadband networks, the types of applications for wireless network become more and more numerous. During the network video/audio transmission and broadcasting, bit error or packet loss often occurs. In general, network video/audio transmission and broadcast technologies use forward error correction (FEC) codes to restore original data or to recover lost packet(s). In general, FEC codes may be deployed in the physical layer, in the media access control (MAC) layer, or in the application layer. In comparison to the FEC codes deployed in the other two-layers, the FEC of the application layer (abbreviated as AL-FEC) has the following features: the supported block length may be longer for providing better error correction capability; since its encode/decode efficiency is high, its implementation only requires software resources so that can be easily deployed on a variety of devices; different block lengths may be selected for different applications to provide flexible error correction capability; and capable of setting different protection parameters for different transmitted data and different packet loss rates.
The Raptor code or the RaptorQ code is one of the common application layer forward error correction (AL-FEC) codes. The request for comments (RFC) document published in the Internet Engineering Task Force (IETF) specifies the implementation details of the Raptor code or the RaptorQ code. As shown in FIG. 1, the Raptor code encoding is basically divided into two stages. The first stage is the pre-encoding operation 110, the second stage is using a common coding mode for encoding, such as the Luby Transform coding (LT coding) operation 120. Most of the time for implementing the Raptor code encoding is spent on the pre-encoding operation of the first stage. The pre-encoding operation pre-codes multiple input symbols, which mainly performs operations for solving simultaneous equations to produce intermediate symbols 130.
After the encoding operation through the complex pre-encoding stage and the LT coding, the Raptor code may produce a very simple output symbol distribution. A paper discloses an encoding algorithm for LT code. This algorithm encodes the input symbols, and each output symbol is the result of the exclusive OR (XOR) operation(s) of one or more input symbols. This encoding method only determines what proportion of the output symbols is formed by a specific number (degree) of the input symbol(s) that are randomly selected. Once the distribution of the specific degree satisfies a specific condition, if the number of the output symbols is slightly higher than the number of the input symbols, the input symbols may be entirely recovered with a high probability.
In the pre-encoding operation of the Raptor code or the RaptorQ code encoding, the Gaussian elimination operation is often used to solve the simultaneous equations. For example, a technical paper discloses a Raptor code decoding technology. This decoding technology uses operation steps of incremental Gaussian elimination to accelerate the Gaussian elimination operation process of single block decoding, to have better efficiency during performing the decoding operation. Besides, a paper discloses a Raptor encoding/decoding technology with modifying a construction method of a matrix A in the 3GPP standard to achieve better operation efficiency of the Gaussian elimination for a single block, wherein the matrix A is used to encode the intermediate symbols into encoded symbols, or decode the received encoded symbols into intermediate symbols.
Another decoding technique of the Raptor code is disclosed for the decoding failure condition where the received encoded symbols are insufficient at a receiver side. This technique continues the reception of encoded symbols even after decoding failure. After receiving enough new encoded symbols, this technique uses a new algorithm to continue the previous decoding progress without restarting the whole decoding operation, to prevent wasting the operations during decoding a single block. A paper discloses the application of decoding Raptor codes in a network coding environment, and adjusts the degree distribution of input symbols with a specific degree of the Raptor code. Thus, the Raptor code may obtain an optimized rate of successful decoding in the network coding environment; this decoding technique uses multiple senders to perform the encoding operation for the same block at the same time, and when each sender performs the decoding operation, there is no any optimized coordination between each other.
There are patent documents disclose encoding and decoding technologies. For example, a patent document discloses an encoding/decoding system architecture based on a chain reaction code. As shown in the system architecture 200 in FIG. 2, based on a series of non-systematic keys I0, I1, . . . and a series of systematic keys C0, C1, . . . , a systematic encoder 210 encodes k input symbols IS(0), IS(1), . . . , IS(K−1). The output after the encoding contains k original input symbols IS(0), IS(1), . . . , IS(K−1), and the repair symbols, denoted by B(I0), B(I1), B(I2), . . . . However, this document does not disclose information about parallelized encoding operations.
A patent document discloses a processing technology of video data. As shown in FIG. 3, at the transmitter end this technology sends the same video source data 310 through several different queues Q1˜Qn to multiple different FEC operation units FEC1˜FECn for performing encoding. Each FEC operation unit uses different error recovery techniques, and then all outputs are merged and transmitted to a network 320. After data is received at the receiver end from the network 320, the data is sent to dedicate FEC decoding unit(s) for performing decoding according to the content of the packet(s).
In the Raptor code or the RaptorQ code encoding, if the time for pre-encoding may be shortened then the overall encoding performance of the Raptor code or the RaptorQ code will be dramatically enhanced. In the aforementioned encoding and decoding technologies, some technologies accelerate the operation process for decoding a single block, which may improve the efficiency of the decoding operation; some technologies use multiple senders at the same time for encoding the same block, but each sender does not coordinate with others for achieving optimized encoding operations; some technologies use parallelized operation units at the sender end of video source data, but the FEC types used in each unit are different. Hence, no parallelized acceleration mechanism is included. For the Raptor encoding operation, it may be observed that the encoding operations among multiple blocks still share a lot of common detailed operations. Therefore, how to dramatically reduce the time of the pre-encoding procedure to enhance the overall encoding throughput of the Raptor code is very important.